package com.example.leetcode.trainingcamp.week7.Thursday;

/**
 * 根据一棵树的中序遍历与后序遍历构造二叉树。
 *
 * <p>注意: 你可以假设树中没有重复的元素。
 *
 * <p>例如，给出
 *
 * <p>中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]
 *
 * <p>来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test106 {
  // 中序遍历 inorder = [9,3,15,20,7]
  // 后序遍历 postorder = [9,15,7,20,3]
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return myTreeBuild(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
  }

    public TreeNode myTreeBuild(int[] inorder,int i,int j,int[] postorder,int k,int l){
        if (k>l) return null;
        TreeNode root = new TreeNode(postorder[l]);
        if (k == l) return root;
        int s = i;
        while (s<=j && inorder[s] != postorder[l]){
            s++;
        }
        int size = s - i;
        TreeNode left = myTreeBuild(inorder,i,i+size -1,postorder,k,k+size-1);
        TreeNode right = myTreeBuild(inorder,i+size+1,j,postorder,k+size,l-1);
        root.left = left;
        root.right = right;
        return root;
    }
}
